package leetcode.dfs;

//200. 岛屿数量
public class NumIslands {


    public int numIslands(char[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    res++;
                }

            }
        }
        return res;
    }

    private void dfs(char[][] grid, int x, int y) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length ||
                grid[x][y] == '0') {
            return;
        }
        grid[x][y] = '0'; //沉岛，避免重复遍历
        int[] dx = {-1, 0, 0, 1};
        int[] dy = {0, 1, -1, 0};
        for (int i = 0; i < 4; i++) {
            int mx = x + dx[i];
            int my = y + dy[i];
            dfs(grid, mx, my);
        }
    }


    // 二战,典型的dfs
    public int numIslandsP(char[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs2(grid, i, j);
                    res++;
                }
            }
        }
        return res;
    }

    private void dfs2(char[][] grid, int x, int y) {
        // 递归出口,要先写边界
        if (x >= grid.length || x < 0 ||
                y >= grid[0].length || y < 0 || grid[x][y] == '0') {
            return;
        }
        // 沉岛
        grid[x][y] = '0';
        int[] dx = {0, 0, -1, 1};
        int[] dy = {1, -1, 0, 0};
        for (int i = 0; i < dx.length; i++) {
            int mx = dx[i] + x;
            int my = dy[i] + y;
            dfs2(grid, mx, my);
        }
    }
}
